console.log("-------插入排序demo---------");
function Insertion(arr) {
  let len = arr.length;
  let preIndex, current;
  // 例如数组 [10,8,4,2,6]
  console.log(arr.join(" ") + "\n");
  /**
   * 第一个元素默认不需要排序，所以从 i = 1 开始
   * 每次遍历，和前一个相邻的元素依次比较
   * 第1轮遍历：
   *    preIndex = 0；arr[preIndex] = 10;  i= 1; current = 8
   *    8 10 4 2 6
   * 第2轮遍历
   *    i = 2; current = 4; preIndex = 1
   *        current < arr[preIndex ,即当前元素更小。
   *            将前一个元素替换为当前元素（当前元素已经暂存）
   *            8 4 10 2 6
   *            前一个元素的指针--，即当前元素再和前面的元素比较
   *            - 8 10 2 6
   *            此时第二轮比较结束，将当前暂时的元素放到正确位置
   *            4 8 10 2 6
   */
  for (let i = 1; i < len; i++) {
    preIndex = i - 1;
    // 核心：暂存当前元素
    current = arr[i];
    while (preIndex >= 0 && current < arr[preIndex]) {
      // 如果当前元素比前一个元素小，则向前移动一位.即前一个元素后移1位
      arr[preIndex + 1] = arr[preIndex];
      //console.log(arr.join(' ')+"\n")
      //指针减1
      preIndex--;
    }
    //当前元素向后移动一位
    arr[preIndex + 1] = current;
    //打印排序
    console.log(arr.join(" ") + "\n");
  }
  return arr;
}
function AnothorInsertion(arr) {
  var len = arr.length;
  for (var i = 1; i < len; i++) {
    var current = arr[i];
    var j = i - 1; //默认已排序的元素Index
    while (j >= 0 && arr[j] > current) {
      //在已排序好的队列中从后向前扫描
      arr[j + 1] = arr[j]; //已排序的元素大于新元素，将该元素移到一下个位置
      j--;
    }
    arr[j + 1] = current;
    console.log(arr.join(" ") + "\n");
  }
  return arr;
}

var arr = [10, 8, 4, 2, 6];
//Insertion(arr);
AnothorInsertion(arr);
